Black Maria ditubuhkan oleh dua orang anak muda yang bersahabat baik iaitu OP (Abdul Rauf Ha) dan Ronnie (Mohd Rosni Jaafar) pada tahun 1998. Mereka membuat keputusan untuk berhijrah dari Kuala Kangsar, Perak, ke Kuala Lumpur dengan hasrat untuk mengembangkan kerjaya seni mereka dengan menubuhkan sebuah kumpulan muzik dan melahirkan album sendiri.

Ketika mereka berdua menetap di Taman Permata, Melawati, Kuala Lumpur, OP sering berkunjung ke sebuah studio muzik yang terkenal di sana iaitu Ima Studio. Selain itu, beliau juga sering melawat ke Heaven Studio milk Mus Satira. Ketika di studio tersebut, OP mula mengenali Lily (pemain gitar bass). Lily yang berasal dari Johor juga sering berkunjung ke studio berkenaan. OP terus mengajak Lily untuk menyertai Black Maria dan Lily bersetuju.

Semasa OP berkerja di sebuah studio lain, beliau mula mengenali CD (Ahmad Rasidi Hamzah). CD yang berasal dari Cheras sering berkunjung ke studio tersebut untuk berlatih bermain dram seorang diri. Apabila OP melihat CD berlatih bermain dram, OP mula menyukai cara permainan CD. Tanpa bertangguh lagi, OP terus mengajak CD untuk menyertai Black Maria dan CD bersetuju kerana beliau sememangnya berminat untuk menyertai sebuah kumpulan muzik.

Tidak lama selepas Lily dan CD menyertai Black Maria bersama OP dan Ronnie, mereka mendapat maklumat bahawa Ali Bakar akan mengadakan sebuah ujibakat untuk mencari sebuah kumpulan muzik rock baru. OP sememangnya menantikan peluang keemasan seperti itu tetapi secara tiba-tiba, Lily tidak mahu ikut serta ke ujibakat tersebut kerana beliau takut kepada Ali Bakar, tanpa menerangkan sebab yang lanjut. OP membuat keputusan untuk menggantikan tempat Lily dengan Sharif yang juga berasal dari Johor. Selepas itu, OP, Ronnie, CD dan Sharif mula berlatih bersama-sama sebagai persediaan sebelum hari ujibakat berlangsung.